#pragma once
#include <iostream>

using namespace std;

//类型为k, 数量为M.
//M层数.
template<class K, size_t M>
struct BTreeNode
{
    //创建关键词数组; 以及相对应的孩子结点.
    K _keys[M];
    //孩子结点的指针.
    BTreeNode<K, M>* _subs[M+1];
    BTreeNode<K, M>* _parent;
    //记录存储关键字数.
    size_t _n;

    BTreeNode()
    {
        for(size_t i = 0; i < M; i++)
        {
            _keys[i] = K();
            _subs[i] = nullptr;
        }
        
        _subs[M] = nullptr;
        _parent = nullptr;
        _n = 0;
    }
};

template<class K, size_t M>
class BTree
{
    typedef BTreeNode<K, M> Node;
public:
    //查找数据:
    pair<Node*, int> Find(const K& key)
    {
        Node* parent = nullptr;
        Node* cur = _root;


        while(cur)
        {
            size_t i = 0;
            while(i < cur->_n)
            {
                //小于关键词不存在.
                if(key < cur->_keys[i])
                {
                    break;
                }
                //大于就在右边.
                else if(key > cur->_keys[i])
                {
                    i++;
                }
                else
                {
                    return make_pair(cur, i);
                }
            }
            //本关键词找不到就到另外一个关键词查看.
            parent = cur;
            cur = cur->subs[i];
        }
        return make_pair(parent, -1);
    }

    //插入关键词:
    void InsertKey(Node* node, const K& key, Node* child)
    {
        int end = node->_n -1;

        while(end >= 0)
        {
            //如果key小于end位置的关键词;
            //那么弄懂关键词, 以及挪动它的右边孩子.
            id(key < node->_keys[end])
            {
                node->_key[end+1] = node->_keys[end];
                node->_subs[end + 2] = node->_subs[end + 1];
                end--;
            }
            else
            {
                break;
            }
        }
        

        //end停止的位置就是插入数据的位置;
        //插入关键词; 以及插入对应的孩子结点.
        //还要更新child结点的父节点.
        node->_keys[end + 1] = key;
        node->_subs[end + 2] = child;
        if(child)
        {
            child->_parent = node;
        }

        node->_n++;
    }

    bool Insert(const K& key)
    {
        //如果树为空.直接插入.
        if(root == nullptr)
        {
            _root = new Node();
            _root->_keys[0] = key;
            _root->_n++;

            return true;
        }


        pair<Node*, int> ret = Find(key);
        //key存在, 不需要插入;
        if(ret.second != -1)
        {
            return false;
        }

        //不存在, 先标志一下父结点和关键词. 以及孩子结点.
        Node* parent = ret.first;
        K newKey = key;
        Node* child = nullptr;

        while(1)
        {
            //插入关键词.
            InsertKey(parent, newKey, child);
            //没有满结束.
            if(parent->_n < M)
            {
                return true;
            }
            //满了就分裂, 分裂一半;
            else
            {
                //找到半数据.
                size_t mid = M / 2;
                Node* brother = new Node;
                size_t j = 0;
                size_t i = mid + 1;


                //将[mid+1, M-1] 给兄弟.
                for(; i <= M - 1; i++)
                {
                    //拷贝左孩子和key.
                    brother->_keys[j] = parent->_keys[i];
                    brother->_subs[j] = parent->_subs[i];

                    if(parent->_subs[i])
                    {
                        parent->_subs->_parent = brother;
                    }
                    j++;

                    parent->keys[i] = K();
                    parent->subs[i] = nullptr;
                }

                //拷贝右孩子;
                brother->_subs[j] = parent->_subs[i];
                if(parent->_subs[i])
                {
                    parent->_subs[i]->parent = brother;
                }
                parent->_subs[i] = nullptr;

                brother->_n = j;
                parent->_n -= (brother->_n + 1);

                K midKey = parent->_keys[mid];
                parent->_keys[mid] = K();
            }
            parent->_subs[i] = nullptr;

            brother->_n = j;
            parent->_n -= (brother->_n + 1);

            K midKey = parent->_key[mid];
            parent->_keys[mid] = K();

            if(parent->_parent == nullptr)
            {
                _root = new Node;
                _root->_keys[0] = midKey;
                _root->_subs[0] = parent;
                _root->subs[1] = brother;
                _root->_n = 1;

                parent->_parent = _root;
                brother->_parent = _root;
                break;
            }
            else
            {
                newKey = midKey;

                child = brother;
                parent = parent->_parent;
            }
        }
    }

    void _InOrder(Node* cur)
    {
        if(cur == nullptr)
            return;
        
        size_t i = 0;
        for(; i < cur->_n; i++)
        {
            //先遍历左子树.
            _InOrder(cur->_subs[i]);
            //打印根子树.
            cout << cur->_keys[i] << " ";
        }

        //再去遍历右子树.
        _InOrder(cur->_subs[i]);
    }

    void InOrder()
    {
        _InOrder(_root);
    }


    void 
private:
    Node* _root = nullptr;
};